package medium;//给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
//
// 说明：每次只能向下或者向右移动一步。
//
//
//
// 示例 1：
//
//
//输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
//输出：7
//解释：因为路径 1→3→1→1→1 的总和最小。
//
//
// 示例 2：
//
//
//输入：grid = [[1,2,3],[4,5,6]]
//输出：12
//
//
//
//
// 提示：
//
//
// m == grid.length
// n == grid[i].length
// 1 <= m, n <= 200
// 0 <= grid[i][j] <= 100
//
// Related Topics 数组 动态规划 矩阵
// 👍 989 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
public class L64 {
    public static int minPathSum(int[][] grid) {
        //动态规划，时间O(n)，空间O(n)
        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = grid.length - 1; i > -1; i--) {
            for (int i1 = grid[0].length - 1; i1 > -1; i1--) {
                if (i == grid.length - 1 && i1 == grid[0].length - 1) {
                    dp[i][i1] = grid[i][i1];
                    continue;
                }

                if (i + 1 == grid.length) {
                    dp[i][i1] = grid[i][i1] + dp[i][i1 + 1];
                } else if (i1 + 1 == grid[0].length) {
                    dp[i][i1] = grid[i][i1] + dp[i + 1][i1];
                } else
                    dp[i][i1] = grid[i][i1] + Math.min(dp[i + 1][i1], dp[i][i1 + 1]);//下面+右边
            }
        }
        return dp[0][0];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
